#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool vis[101][101];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

bool exist(vector<string>& board, string word) {
    // write code here
    n = board.size(), m = board[0].size();

    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            if (board[i][j] == word[0])
                if (dfs(board, word, i, j, 0))
                    return true;

    return false;
}

bool dfs(vector<string>& board, string word, int x, int y, int pos)
{
    if (pos == word.size() - 1)
    {
        return true;
    }

    vis[x][y] = true;

    for (int i = 0;i < 4;i++)
    {
        int a = x + dx[i];
        int b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && board[a][b] == word[pos + 1])
            if (dfs(board, word, a, b, pos + 1))
                return true;
    }

    vis[x][y] = false;

    return false;

}int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

bool dfs(vector<string>& board, string word, int x, int y, int pos)
{
    if (pos == word.size() - 1)
    {
        return true;
    }

    vis[x][y] = true;

    for (int i = 0;i < 4;i++)
    {
        int a = dx[i] + x;
        int b = dy[i] + y;
        if (a >= 0 && a < m && b >= 0 && b < m && !vis[a][b] && board[a][b] == word[pos + 1])
            if (dfs(board, word, a, b, pos + 1))
                return true;
    }

    vis[x][y] = false;

    return false;

}

bool exist(vector<string>& board, string word) {
    // write code here
    n = board.size(), m = board[0].size();

    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            if (board[i][j] == word[0])
                if (dfs(board, word, i, j, 0))
                    return true;

    return false;
}



int main()
{
    vector<string> board = {"aa" };
    string world = "aaa";

    exist(board, world);

	return 0;
}